package com.bo.day20231222;

import java.util.Stack;

/**
 * 迭代方式实现
 *
 * @Author: gpb
 * @Date: 2024/1/3 16:19
 * @Description:
 */
public class UnRecursiveTraversalBT {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node (int v) {
            value = v;
        }
    }

    /**
     * 前序遍历：头左右
     *
     * @param cur
     */
    public static void pre (Node cur) {
        System.out.println("先序遍历");
        if (cur == null) {
            return;
        }
        // 先序：头,左,右
        // 使用栈的方式 先序遍历二叉树
        // 流程：
        // cur 为当前节点
        // 1.添加头节点
        // 遍历：先添加cur的右节点,然后添加cur的左节点
        // 然后弹出元素依次,先添加cur的右节点,然后添加cur的左节点
        // 先序的顺序是：头,左,右,为什么要先添加右节点呢?
        // 因为栈结构：先进后出,后进先出
        Stack<Node> stack = new Stack<>();
        stack.push(cur);
        while (!stack.isEmpty()) {
            cur = stack.pop();
            System.out.println(cur.value);
            // 先右边,在左
            if (cur.right != null) {
                stack.push(cur.right);
            }
            // 左边
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

    /**
     * 后序遍历：左右头
     *
     * @param cur
     */
    public static void pos (Node cur) {
        System.out.println("后序遍历");
        if (cur == null) {
            return;
        }
        // 先添加头,左,右
        Stack<Node> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        stack1.add(cur);
        while (!stack1.isEmpty()) {
            cur = stack1.pop();
            stack2.add(cur.value);
            if (cur.left != null) {
                stack1.push(cur.left);
            }
            if (cur.right != null) {
                stack1.push(cur.right);
            }
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop() + " ");
        }
    }

    public static void pos2 (Node h) {
        if (h == null) {
            return;
        }
        /*
         * 后序遍历方式：左,右,头
         * 一个栈实现思路
         * 1)  当前节点cur,cur的左节点不等于h节点,cur的右节点不等于h节点,当前节点进栈
         * 2)  当前节点cur的右节点不等空,cur的右节点不等于h节点,当前节点进栈
         * 3)  当前节点左右子树为空的时候或者当前节点的左右子树其中有个等于h节点,那么就打印,h节点重新赋值为cur节点
         * */
        Stack<Node> stack = new Stack<>();
        stack.push(h);
        Node cur = null;
        while (!stack.isEmpty()) {
            cur = stack.peek();
            if (cur.left != null && cur.left != h && cur.right != h) {
                stack.push(cur.left);
            } else if (cur.right != null && cur.right != h) {
                stack.push(cur.right);
            } else {
                System.out.print(stack.pop().value + " ");
                h = cur;
            }
        }

    }

    /**
     * 中序遍历：左，头，右
     *
     * @param cur
     */
    public static void in (Node cur) {
        System.out.println("中序遍历");
        if (cur == null) {
            return;
        }
        /*
         * 实现思路：
         * 1) 当前节点cur,cur头树,整条左边界进栈,直到遇到空
         * 2) 栈中弹出节点打印,节点的右孩子为cur 转步骤1
         * 3) 栈为空停止
         * */
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || cur != null) {
            //  当前节点cur,cur头树,整条左边界进栈
            if (cur != null) {
                stack.push(cur);
                // 整条左边界进栈
                cur = cur.left;
            } else {
                // 栈中弹出节点打印,节点的右孩子为cur
                cur = stack.pop();
                System.out.print(cur.value + " ");
                cur = cur.right;
            }
        }
    }

    public static void main (String[] args) {
        Node node = new Node(1);
        node.left = new Node(5);
        node.right = new Node(6);
        node.left.left = new Node(3);
        node.left.right = new Node(8);
        node.left.left.left = new Node(2);
        node.right.left = new Node(7);
        node.right.right = new Node(4);
        pos(node);
        System.out.println();
        pos2(node);
    }

}
